package zuochengyun;

//在两个长度相等的排序数组中找到上中位数	P465
//关联题目，KthMinOfTwoSortedArray
public class UpMedianOfTwoSortedArray {

	//两个数组都是排好序的，且长度相等，求组成的数组中的上中位数
	public int getUpMedian(int[] arr1, int[] arr2){
		if(arr1 == null || arr2 == null || arr1.length != arr2.length){
			throw new IllegalArgumentException("the input is invalid");
		}
		int start1 = 0;
		int end1 = arr1.length - 1;
		int start2 = 0;
		int end2 = arr2.length - 1;
		int mid1 = 0;
		int mid2 = 0;
		int offset = 0;		//用来判断数组是奇数还是偶数个
		//注意，两个数组的长度始终要保持一样
		while(start1 < end1){
			mid1 = (start1 + end1) / 2;
			mid2 = (start2 + end2) / 2;
			offset = ((end1 - start1 + 1) & 1) ^ 1;		//为奇数时为0，偶数是为1
			if(arr1[mid1] == arr2[mid2]){
				//显然如果相等就可以直接返回
				return arr1[mid1];
			}else if(arr1[mid1] > arr2[mid2]){
				//如果不相等，那么就需要二分。比如[1 2 3 4 5](数字代表是第几个数，并不是值)
				//[1'  2'  3'  4'  5'](同上，表示第二个数组的第几个数)
				//如果 3 > 3', 那么说明4  5 肯定不可能是，1'  2' 肯定不可能是，所以只有[1 2 3]和[3'  4'  5']
				//于是end1 = mid1， start2 = mid2 
				//对于偶数的不一样，所以我们需要一个offse
				end1 = mid1;
				start2 = mid2 + offset;
			}else{
				//对于小于的情况，同理分析
				end2 = mid2;
				start1 = mid1 + offset;
			}
		}
		
		return Math.min(arr1[start1], arr2[start2]);
	}
}
